Projektuppgift

Algebra och diskret matematik

Högskolan i Halmstad

Dawid Ejdeholm, Jacob Harsten & Harald Lilja

Uppgift 1

Beräkna (7^82) mod 100

(a^(ϕ(n)))≡1(mod n) (Då a och n är relativt prima)

EulerPhi[100]

Då får vi att
(7^(ϕ(100)))≡1(mod 100) = (7^40)≡1 (mod 100)
(7^82)=(7^40)× (7^40)× (7^2)≡1×1×(7^2)=49 (mod 100)

PowerMod[7,82,100]

Uppgift 2

Beräkna (572^29) mod 713 med hjälp av “kvadreringsmetoden” ovan.

(572^29) = (572^16) × (572^8)×(572^4)×(572^1)

(572^1) ≡ 572 (mod 713)
(572^2) = 327184 = 713 × 458 + 630 ≡ 630 (mod 713)
(572^4)= ((((572^2)))^2) ≡(630^2) = 396900 = 713 556+472 ≡472(mod 713) 
(572^8)= ((((572^4)))^2) ≡(472^2) = 222784 = 713 312+328 ≡328(mod 713) 
(572^16)= ((((572^8)))^2) ≡(328^2) = 107584 = 713 150+634 ≡634(mod 713) 
(572^29)=634×328×472×572 =207952×269984≡469 ×470=220430≡113 (mod 713)

Svar: (572^29)≡113(mod 713)

PowerMod[572,29,713]

Uppgift 3

Bestäm primtalen p och q om n = pq = 39247771 och ϕ(n) = 39233944

n - ϕn = pq - (p-1)(q-1)

39247771-39233944=13827
pq-qp+p+q-1=13827
p+q-1=13827
p+q=13828

pq=3924771

pq = 13828q-(q^2)
(q^2)-13828q+pq=0

q=(13828/2)±(Sqrt[((((13828/2)))^2)-pq])

q = 6914±2925

(Subscript[q, 1])=6914-2925=3989
(Subscript[q, 2])=6914+2925=9839

3989*9839

PrimeQ[3989]

PrimeQ[9839]

Uppgift 4

För heltalen a och b gäller att b≡a (mod 91) och sgd(a,91) = 1. Bestäm et positivt tal k > 1 sådant att (b^k)≡a (mod 91). Vad är a mod 91 om b = 53?

Divisionsalgoritmen:
ed≡1 (mod ϕ(n)) sådana att ed = kϕ(n)+1

EulerPhi[91]

n = 91
SGD(a,91)≡1 => (a^72)≡1(mod 91)
b = 53
(b^k)≡a (mod 91)

k = cϕ(n)+1=c72+1=1*72+1=73
Där c kan vara alla positiva heltal c>0.

(b^k)=(b^73)=(53^73)≡a (mod 91)
Eftersom (53^73) och är a är kongurrenta med 91 vet vi att a = 53

Solve[{53^73==a},Modulus->91]

Uppgift 5

Bestäm några olika värden på e om p = 19 och q = 13. Välj därefter ett av värdena på e, bestäm d och kryptera meddelandet M = 10. Kontrollera dina beräknignar genom att avkryptera det krypterande meddelandet. Vilka meddelanden (tal) M krypteras med ovanstående nycklar?

p=19;
q=13;
n=p*q;
e =49;

Vi valde e = 49 för 49 och 216 är relativt prima.

EulerPhi[n]

GCD[49,216]

Euklides på SGD(216,46) ger
216 = 4×49+20
49 = 2×20+9
20 = 2×9+2
9 = 4×2+1
2 = 2×1

med hjälp av euklides baklänges får vi den diofantiska ekvationen
49d + 216k = 1
d = 97
k = -22

Clear[d];
Clear[k];
Reduce[49d+216k==1,{d,k},Integers]

Krypterat
(M^e) mod n = (10^49) mod 247

PowerMod[10,49,247]

Avkrypterat
(M^e) mod n = (10^49) mod 247

PowerMod[127,97,247]

M måste vara mindre än n (247 i detta fall).

Uppgift 6

Skriv ett program i Mathematica som krypterar och avkrypterar ett godtyckligt textmeddelande.
Använd Unicode för tecknen då meddelandet transformeras till ett heltal och kryptera/avkryptera ett tecken i taget. Indata till programmet ska vara textmeddelandet, samt antalet siffror i primtalen q och p. Dessa ska sedan genereras slumpmässigt.

Kryptering

text=InputString["Texten du vill kryptera"];
primeNr =Input["Välj hur stort primtal","Välj ett tal större än 1"];
p = RandomPrime[{(10^(primeNr-1)),(10^primeNr)-1}];
q = RandomPrime[{(10^(primeNr-1)),(10^primeNr)-1}];
e = 1283;
n = p*q;
Medd = ToCharacterCode[text,"Unicode"];
kryptMedd = PowerMod[Medd, e, n];
kryptMedd

GCD[e,EulerPhi[n]]

Avkryptering

Clear[d];
Clear[b];
temp = Table[Reduce[d*e+b*EulerPhi[n]==1,{d,b},Integers],{1}];
d=temp[[1,2,2,1]];
avkryptMedd =FromCharacterCode[PowerMod[kryptMedd,d,n],"Unicode"];
avkryptMedd